package QuestionDaily;

import java.util.*;

public class carPooling_1094 {
    /**
     * 题目解释参照leetcode
     * @param trips  trip[i] = [p, f, t] 表示第 i 次旅行有 p 名乘客，
     * 接他们和放他们的位置分别是 f 和 t。这些位置是从汽车的初始位置向东的公里数。
     * @param capacity 车上最初有 capacity 个空座位
     * @return
     */
    public boolean carPooling(int[][] trips, int capacity) {
        /**
         * 思路就是记录需要停车的位置，然后算出该位置的人员变化
         * 5ms
         */
        int persons=0;  //车上的乘客数量
        HashMap<Integer, Integer> map=new HashMap<>();
        //需要停车的位置以及该位置上车的人数（为负数说明下车的人比上车的人多），根据位置维护成升序
        for(int i=0;i<trips.length;i++){
            if(map.get(trips[i][1])!=null){          //添加上车点
                int a=map.get(trips[i][1]);
                map.put(trips[i][1],a+trips[i][0]);
            }else
                map.put(trips[i][1],trips[i][0]);
            if(map.get(trips[i][2])!=null){          //添加下车点
                int a=map.get(trips[i][2]);
                map.put(trips[i][2],a-trips[i][0]);
            }else
                map.put(trips[i][2],-trips[i][0]);
        }
        Set<Integer> set=map.keySet();
        Object[] arr=set.toArray();
        Arrays.sort(arr);
        for(Object key:arr){
            persons+=map.get(key);
            if(persons>capacity)
                return false;  //有一个停车位置车内人数超出即可返回false
        }
        return true;
    }

    /**
     * 高解，使用有限容量的数组，感觉有点走捷径的意思
     * 思路都是一样的
     * @param trips
     * @param capacity
     * @return
     */
    public boolean carPooling2(int[][] trips, int capacity) {
        int[] capacityChanges = new int[1001];
        for (int i = 0; i < trips.length; i++) {
            capacityChanges[trips[i][1]] -= trips[i][0];
            capacityChanges[trips[i][2]] += trips[i][0];
        }

        for (int i = 0;i < capacityChanges.length;i++) {
            capacity += capacityChanges[i];
            if (capacity < 0) {
                return false;
            }
        }
        return true;
    }
}
